package code1.graph;

import java.util.*;

public class P200 {

    int n,m;
    int cnt=0;
    boolean[][] visited;
    int[][] go={{1,0},{-1,0},{0,-1},{0,1}};

    void dfs(int x,int y,char[][] grid){
        for(int i=0;i<4;i++){
            int nextx=x+go[i][0];
            int nexty=y+go[i][1];
            if(nextx>=0 && nextx<n && nexty>=0 && nexty<m && grid[nextx][nexty]=='1' && !visited[nextx][nexty]){
                visited[nextx][nexty]=true;
                dfs(nextx,nexty,grid);
            }
        }
    }

    void bfs(int x,int y,char[][] grid){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            for(int i=0;i<4;i++){
                int nextx=point[0]+go[i][0];
                int nexty=point[1]+go[i][1];
                if(nextx>=0 && nextx<n && nexty>=0 && nexty<m && grid[nextx][nexty]=='1' && !visited[nextx][nexty]){
                    visited[nextx][nexty]=true;
                    queue.offer(new int[]{nextx,nexty});
                }
            }
        }
    }


    public int numIslands(char[][] grid) {
        n=grid.length;
        m=grid[0].length;
        visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && grid[i][j]=='1'){
                    cnt++;
                    visited[i][j]=true;
                    bfs(i,j,grid);
                    //dfs(i,j,grid);
                }
            }
        }
        return cnt;
    }
}
